package addressBook;

import javax.xml.transform.sax.SAXTransformerFactory;
import java.util.Stack;

/**
 * @author Jarvan
 * @version 1.0
 * @create 2020/11/12 21:44
 */
public class BinarySearchTree<E extends Comparable<E>> extends BaseBinaryTree<E>{

    /**
     * addressBook.BaseBinaryTree
     */
    private BaseBinaryTree<E> baseTree;
    /**
     * NoArgsConstructor
     */
    public BinarySearchTree() {
        this.baseTree = new BaseBinaryTree<>();
    }

    /**
     *  Search a item of the binary tree.
     * @param contactKey  contactKey contactKey search key.
     * @return  contactKey contactKey search key.
     */
    public TreeNode<E> searchItem(E contactKey) {
        return searchItem(this.baseTree,contactKey);
    }
    /**
     * Insert a new Item of the binary tree.
     *
     * @param element new item.
     * @return whether the item insert success.
     */
    public boolean insertItem(E element) {
        return insertItem(this.baseTree,element);
    }


    /**
     * Search a item of the binary tree.
     * @param baseTree baseTree
     * @param contactKey contactKey search key.
     * @return  contactKey contactKey search key.
     */
    private TreeNode<E> searchItem(BaseBinaryTree<E> baseTree,E contactKey) {
        if (baseTree == null) {
            throw new TreeException();
        }
        TreeNode<E> root = baseTree.getRoot();
        while (root != null) {
            if (contactKey.compareTo(root.element) < 0){
                root = root.left;
            }else if (contactKey.compareTo(root.element) > 0){
                root = root.right;
            } else if (contactKey.compareTo(root.element) == 0) {
                return root;
            }
        }
        return null;
    }
    /**
     * Remove a element. There 3 situations.
     * * 1. removeElement is leaf node(no left subtree or right subtree),just let target equal null.
     * * 2. removeElement just have a subNode,just let target equal null and , value that node.data as subNode.
     * * 3. removeElement has two subNodes ,**use the smallest node in right subtree replace remove target node ,
     *      and remove the smallest node in right subtree.**
     * @param removeElement element.
     * @return return true if remove success.
     */
    public boolean remove(E removeElement) {
        return removeItemByKey(this.baseTree,removeElement);
    }
    /**
     * Insert a new Item of the binary tree.
     *
     * @param element new item.
     * @return whether the item insert success.
     */
    private boolean insertItem(BaseBinaryTree<E> baseTree,E element) {
        TreeNode<E> root = baseTree.getRoot();
        TreeNode<E> node = new TreeNode<>();
        node.setElement(element);
        if (root == null) {
            root = node;
            baseTree.setRoot(root);
            return true;
        }
        while (root != null){
            int elemCompareRoot = element.compareTo(root.element);
            //insert element small. insert in left.
            if (elemCompareRoot < 0){
                if (root.left == null){
                    root.left = node;
                    return true;
                }
                else {
                    //如果不为空将替换之前的值，然后root继续
                    root = root.left;
                }
            }//insert element large ,insert in right.
            else if (elemCompareRoot > 0){
                if (root.right == null) {
                    root.right = node;
                    return true;
                }else{
                    root = root.right;
                }
            }
        }
        //insert element equal one of a element of tree. return false.
        return false;
    }


    /**
     * Remove a element. There 3 situations.
     * * 1. removeElement is leaf node(no left subtree or right subtree),just let target equal null.
     * * 2. removeElement just have a subNode,just let target equal null and , value that node.data as subNode.
     * * 3. removeElement has two subNodes ,**use the smallest node in right subtree replace remove target node ,
     *      and remove the smallest node in right subtree.**
     * @param baseTree baseTree
     * @param removeElement element.
     * @return return true if remove success.
     */
    private boolean removeItemByKey(BaseBinaryTree<E> baseTree,E removeElement) {
        if (baseTree.root != null){
            TreeNode<E> searchItem = searchItem(baseTree, removeElement);
            //1.removeElement is leaf node(no left subtree or right subtree),just let target equal null.
            if (searchItem.left == null && searchItem.right == null) {
                searchItem = null;
                return true;
            }
            //2.removeElement just have a subNode,just let target equal null and , value that node.data as subNode.
            else if (searchItem.left == null){
                //store successor element value.
                searchItem.element = searchItem.right.element;
                //successor the right.right subtree.
                if (searchItem.right.right!=null){
                    searchItem.right = searchItem.right.right;
                }
                //successor the right.left subtree
                if (searchItem.right.left != null){
                    searchItem.left = searchItem.right.left;
                }
                return true;
            }else if (searchItem.right == null){
                searchItem.element = searchItem.left.element;
                if (searchItem.left.right !=null){
                    searchItem.right = searchItem.left.right;
                }
                if (searchItem.left.left !=null){
                    searchItem.left = searchItem.left.left;
                }
                return true;
            }else {

                //[this is the most difficult part of delete.]
                //1.find the successorParent
                TreeNode<E> successorParent = findSuccessorParent(searchItem);
                //2. valuation the current.element = successorParent.left.element
                searchItem.element = successorParent.left.element;
                //3.1 不是叶子的时候
                //3.1 successorParent.left = successorParent.left.right
                if (successorParent.left.right !=null){
                    successorParent.left = successorParent.left.right;
                }
                //是叶子的时候. 删除
                else {
                    successorParent.left = null;
                }
                return true;

            }

        }
        return false;
    }
    private TreeNode<E> findSuccessorParent(TreeNode<E> currentNode){
        TreeNode<E> node = currentNode;
        TreeNode<E> parent;
        Stack<TreeNode<E>> stack = new Stack<>();
        while (node!=null || !stack.isEmpty()){
            while (node != null){
                stack.push(node);
                node = node.left;
            }
            //stack is not empty .
            if (!stack.isEmpty()){
                stack.pop();
                return stack.pop();
            }

        }
        return null;
    }

    /**
     * Returns a Tree iterator reference.
     *
     * @return Returns a Tree iterator reference.
     */
    public TreeIterator<E> iterator() {
        return new TreeIterator<E>(this.baseTree);
    }

}
